package com.asia.algorithmcode.binaryTree;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @DESCRIPTION: 96、不同的二叉搜索树
 * @USER: wanfu
 * @DATE: 2025/4/24 星期四 11:13
 */
public class GenerateTrees {

    public static void main(String[] args) {

        System.out.println(new GenerateTrees().generateTrees(3));
    }


    public Integer generateTrees(int n) {
        // 递推式子 f(n) = f(j-1) * f(i-j) 最终结果是  i从1到n的f(j-1) * f(i-j) 的Σ
        int[] resArr = new int[n + 1];
        resArr[0] = 1;

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                resArr[i] += resArr[j - 1] * resArr[i - j];
            }
        }
        return resArr[n];
    }


//    public Integer generateTrees(int n) {
//        if (n == 0) {
//            return 0;
//        }
//        return dfs(1, n);
//    }

    /**
     * dfs 深度优先遍历
     *
     * @param l
     * @param r
     * @return
     */
    private Integer dfs(int l, int r) {
        int count = 0;
        if (l > r) {
            return 0;
        }
        for (int i = l; i <= r; i++) {
            int left = dfs(l, i - 1);
            int right = dfs(i + 1, r);
            count += (left == 0 ? 1 : left) * (right == 0 ? 1 : right);
        }
        return count;
    }


}
